#import "IOrderedListD.h"
#import <objc/hashtable.h>
#import <string.h>

@implementation IOrderedListD

- initWithKey:(const char *)aKey
{
    [super init];
    key = NXCopyStringBufferFromZone(aKey, [self zone]);
    return(self);
}

- (const char *)key
{
    return(key);
}

- free
{
    NXZoneFree([self zone], key);
    [self freeObjects];
    return([super free]);
}

- (BOOL)insertKeyedObject:(IKeyedObject *)theObject
{
    unsigned int index;
    BOOL flag;

    index = [self indexForKey:[theObject key] exists:&flag];
    if (flag == NO) {
        [self insertObject:theObject at:index];
        return(YES);
    } else {
        return(NO);   
    }
}

- objectWithKey:(const char *)theKey
{
    unsigned int index;
    BOOL flag;

    index = [self indexForKey:theKey exists:&flag];
    if (flag == YES) {
        return([self objectAt:index]);
    } else {
        return(nil);   
    }
}

- dataForKey:(const char *)theKey
{
    return([self objectWithKey:theKey]);
}

- (BOOL)removeObjectWithKey:(const char *)theKey
{
    unsigned int index;
    BOOL flag;

    index = [self indexForKey:theKey exists:&flag];
    if (flag == YES) {
        [self removeObjectAt:index];
        return(YES);
    } else {
        return(NO);   
    }
}

- (BOOL)removeDataForKey:(const char *)theKey
{
    return([self removeObjectWithKey:theKey]);
}

- (unsigned int)indexForKey:(const char *)theKey exists:(BOOL *)flag
{
    unsigned int lowerBound, midPoint, upperBound;
    int strcmpResult;

    if (numElements == 0) {
        *flag = NO;
        return(0);
    }
    lowerBound = 0;
    upperBound = numElements - 1;
    strcmpResult = strcmp(theKey, [[self objectAt:lowerBound] key]);
    if (strcmpResult == 0) {
        *flag = YES;
        return(lowerBound);
    }
    if (strcmpResult < 0) {
        *flag = NO;
        return(lowerBound);
    }
    strcmpResult = strcmp(theKey, [[self objectAt:upperBound] key]);
    if (strcmpResult == 0) {
        *flag = YES;
        return(upperBound);
    }
    if (strcmpResult > 0) {
        *flag = NO;
        return(upperBound + 1);
    }
    while(upperBound - lowerBound > 1) {
        midPoint = (lowerBound + upperBound) / 2;
        strcmpResult = strcmp(theKey, [[self objectAt:midPoint] key]);
        if (strcmpResult == 0) {
            *flag = YES;
            return(midPoint);
        } else if (strcmpResult < 0) {
            upperBound = midPoint;
        } else {
            lowerBound = midPoint;
        }
    }
    *flag = NO;
    return(upperBound);
}

@end
